class Solution {
public:
//     void dfs(int n)
//     {
//         if (left_sum < n)
//         {
//             left_sum++;
//             left_lv++;
//             path += '(';
//             dfs(n);

//             path.pop_back();
//             left_sum--;
//             left_lv--;
//         }

//         if (left_lv > 0)
//         {
//             cnt++;
//             left_lv--;
//             path += ')';
//             dfs(n);

//             path.pop_back();
//             cnt--;
//             left_lv++;
//         }
        
//         if (cnt == n)
//         {
//             ret.push_back(path);
//         }
//     }
//     vector<string> generateParenthesis(int n) {
//         path += '(';
//         dfs(n);
//         return ret;
//     }
// private:
//     vector<string> ret;
//     string path;
//     int left_lv = 1;   //记录没有被匹配的左括号个数
//     int left_sum = 1;   //记录左括号的总个数
//     int cnt = 0;    //记录已经生成的括号个数


    void dfs(int n)
    {
        if (left < n)
        {
            left++;
            path += '(';
            dfs(n);

            path.pop_back();
            left--;
        }

        if (right < left)
        {
            right++;
            path += ')';
            dfs(n);

            path.pop_back();
            right--;
        }
        
        if (right == n)
        {
            ret.push_back(path);
        }
    }
    vector<string> generateParenthesis(int n) {
        path += '(';
        dfs(n);
        return ret;
    }
private:
    vector<string> ret;
    string path;
    int left = 1;   //记录左括号的总个数
    int right = 0;   //记录右括号的个数
};